/*
提交链接：https://leetcode.cn/problems/delete-operation-for-two-strings/description/
583.两个字符串的删除操作
刘思琪 2024/9/8
*/

class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1=word1.size(),l2=word2.size();
        int dp[550][550];
        for(int i=1;i<=l1;i++){                  //找到公共子序列
            char a=word1[i-1];
            for(int j=1;j<=l2;j++){
                char b=word2[j-1];
                if(a==b)
                dp[i][j]=dp[i-1][j-1]+1;
                else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return (l1-dp[l1][l2])+(l2-dp[l1][l2]);     //计算要删除的字符个数
    }
};